package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/10/30 10:12
 */
public class LC79单词搜索 {

    private static final int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && backtracking(board, i, j, 0, word, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABC";
        System.out.println(exist(board, word));
    }

    private static boolean backtracking(char[][] board, int row, int col, int wordIndex, String word, boolean[][] visited) {
        if (word.charAt(wordIndex) != board[row][col]) return false;
        if (wordIndex == word.length() - 1) return true;

        visited[row][col] = true;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0], nextCol = col + dir[1];
            if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length) continue;
            if (!visited[nextRow][nextCol] && backtracking(board, nextRow, nextCol, wordIndex + 1, word, visited)) {
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
}
